package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 1130. 叶值的最小代价生成树
 * @author feizns
 * @since 2020/3/17
 */
public class MctFromLeafValues {

    public static void main(String[] args) {
        System.out.println(new MctFromLeafValues().mctFromLeafValues(new int[]{1, 2, 3, 4}));
    }

//    public int mctFromLeafValues(int[] arr) {
//        if (arr == null || arr.length == 0)
//            return 0;
//        int n = arr.length;
//        memoization = new int[n][n];
//        return getMinSum(arr, 0, arr.length - 1);
//    }
//
//    private int[][] memoization;
//
//    private int getMinSum(int[] arr, int left, int right) {
//        if (left == right) {
//            return 0;
//        }
//        if (memoization[left][right] != 0)
//            return memoization[left][right];
//        int minSum = Integer.MAX_VALUE;
//        for (int i = left; i < right; i++) {
//            int leftStart = left, leftEnd = i, rightStart = i + 1, rightEnd = right;
//            int temp = getMinSum(arr, leftStart, leftEnd) + getMinSum(arr, rightStart, rightEnd) +
//                    getMaxNum(arr, leftStart, leftEnd) * getMaxNum(arr, rightStart, rightEnd);
//            minSum = Math.min(temp, minSum);
//        }
//        memoization[left][right] = minSum;
//        return minSum;
//    }
//
//    private int getMaxNum(int[] arr, int left, int right) {
//        int max = Integer.MIN_VALUE;
//        for (int i = left; i <= right; i++) {
//            max = Math.max(max, arr[i]);
//        }
//        return max;
//    }

    public static int mctFromLeafValues(int[] arr) {
        m = new int[arr.length][arr.length];
        return getMin(arr, 0, arr.length - 1);
    }

    static int[][] m;

    private static int getMin(int[] arr, int l, int r) {
        if ( l >= r )
            return 0;
        if ( m[l][r] != 0 )
            return m[l][r];
        int min = Integer.MAX_VALUE;
        for (int i = l; i < r; i++) {
            int ls = l;
            int le = i;
            int rs = i + 1;
            int re = r;
            int lv = getMin(arr, ls, le);
            int rv = getMin(arr, rs, re);
            int cu = max(arr, ls, le) * max(arr, rs, re);
            min = Math.min(lv + rv + cu, min);
        }
        m[l][r] = min;
        return min;
    }

    private static int max(int[] arr, int l, int r) {
        int max = Integer.MIN_VALUE;
        for (int i = l; i <= r; i++)
            max = Math.max(arr[i], max);
        return max;
    }

}
